package foundation.图论.最短路;

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * {@code dijkstra} 算法
 * <p>
 * 给定一个源点，求解从源点到每个点的最短路径长度。单源最短路径算法。
 * <p>
 * 适用范围：有向图、边的权值没有负数
 * <p>
 * 实现方式：
 * <ul>
 *     <li><strong>普通堆实现的 Dijkstra 算法</strong>：最普遍、最常用
 *         <p>算法核心过程：
 *         <ol>
 *             <li>节点弹出过就忽略</li>
 *             <li>节点没弹出过，让其它没弹出节点距离变小的记录加入堆</li>
 *         </ol>
 *     </li>
 *     <li><strong>反向索引堆实现的 Dijkstra 算法</strong>：最快速、最极致
 *         <p>核心在于掌握反向索引堆</p>
 *     </li>
 * </ul>
 */
public class Dijkstra {
    static int MAXN = 101;
    static int MAXM = 6001;

    static int[] head = new int[MAXN];
    static int[] next = new int[MAXM];
    static int[] to = new int[MAXM];
    static int[] weight = new int[MAXM];

    static int[] dist = new int[MAXN];
    static boolean[] visited = new boolean[MAXN];


    static int INF = Integer.MAX_VALUE;
    static int cnt;


    public static void add(int u, int v, int w) {
        next[cnt] = head[u];
        to[cnt] = v;
        weight[cnt] = w;
        head[u] = cnt++;
    }

    public static void init() {
        cnt = 1;
        Arrays.fill(head, 0);
        Arrays.fill(dist, INF);
        Arrays.fill(visited, false);
    }

    /**
     * 算法
     *
     * @param s 出发点
     */
    private static void dijkstra(int s) {
        dist[s] = 0;
        PriorityQueue<int[]> heap = new PriorityQueue<>(Comparator.comparingInt(a -> a[1]));
        heap.add(new int[]{s, 0});
        while (!heap.isEmpty()) {
            int u = heap.poll()[0];
            if (!visited[u]) {
                visited[u] = true;
                // u ->  v   w
                for (int ei = head[u]; ei != 0; ei = next[ei]) {
                    int v = to[ei];
                    int w = weight[ei];
                    if (!visited[v] && dist[v] > dist[u] + w) {
                        // v 要更新,并放入队列
                        dist[v] = dist[u] + w;
                        heap.add(new int[]{v, dist[u] + w});
                    }
                }
            }
        }
    }

    public int networkDelayTime(int[][] times, int n, int k) {
        init();
        for (int[] time : times) {
            add(time[0], time[1], time[2]);
        }
        dijkstra(k);
        int ans = -1;
        for (int i = 1; i <= n; i++) {
            ans = Math.max(ans, dist[i]);
        }
        return ans == INF ? -1 : ans;
    }


}
